/*
 * Nancy Qiannan Zhang
 * Andrew ID: qiannanz
 * 
 * Mita Yipeng Yun
 * Andrew ID: yipengy
 */

package edu.cmu.cs211.bacon.cable;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.List;

import edu.cmu.cs211.bacon.util.Dijkstra;
import edu.cmu.cs211.bacon.util.Edge;
import edu.cmu.cs211.bacon.util.GeneralGraph;
import edu.cmu.cs211.bacon.util.Kruskal;

public class BaconCableCompany {

	/**
	 * @param inputEdges 
	 *      The set of possible CableWires and their costs
	 *
	 * @throws NullPointerException
	 *      If inputEdges is null
	 *      
	 * @returns
	 *      A minimum-cost set of edges that allows the BaconCableCompany to
	 *      provide service to every location.  <tt>null</tt> is returned if
	 *      no set of edges would allow the BaconCableCompany to reach every
	 *      location starting from a single location.
	 */
	public static Set<CableWire> getMst(Set<CableWire> inputEdges) {
		if(inputEdges == null)
			throw new NullPointerException();
		//the set that contain the edges for the graph
		HashSet<Edge<String>> edges = new HashSet<Edge<String>>();
		//the set that contain the vertices for the graph
		HashSet<String> vertices = new HashSet<String>();
		Iterator<CableWire> itr_cable = inputEdges.iterator();
		//construct graph from inputEdges
		while(itr_cable.hasNext()){
			CableWire temp = itr_cable.next();
			vertices.add(temp.getFirstLocation());
			vertices.add(temp.getSecondLocation());
			edges.add(new Edge<String>(temp.getFirstLocation(),
					temp.getSecondLocation(),temp.getCost()));
		}
		GeneralGraph<String, Edge<String>> g = new GeneralGraph<String, Edge<String>>(vertices,edges);
		//use Kruskal to get MST
		Kruskal kk = new Kruskal();
		List<Edge<String>> temp = kk.spanningTree(g);
		if(temp == null)
			return null;
		//result set
		HashSet<CableWire> res = new HashSet<CableWire>();
		Iterator<Edge<String>> itr = temp.iterator();
		while(itr.hasNext()){
			Edge<String> next = itr.next();
			res.add(new CableWire(next.src(),next.dest(),next.weight()));
		}
		return res;
	}

	/**
	 * @param inputEdges
	 *      The set of possible CableWires and their costs
	 *
	 * @param source
	 *      the first location in the requested path
	 *
	 * @param dest
	 *      the last location in the requested path
	 *
	 * @throws NullPointerException
	 *      if inputEdges is null
	 *
	 * @throws IllegalArgumentException
	 *      if source or dest could not be found in inputEdges
	 *     
	 * @returns
	 *      An ordered list of CableWires that form a path from the source location
	 *      to the dest location. Every CableWire in this path must also be contained
	 *      in the minimum-cost set of edges that allows the BaconCableCompany to
	 *      provide service to every location.  <tt>null</tt> is returned if
	 *      no such path can be found.
	 */
	public static List<CableWire> pathUsingMst(Set<CableWire> inputEdges, String source, String dest) {
		if(inputEdges == null)
			throw new NullPointerException();
		
		//iterate through inputEdges to count the number of sources and destinations occured.
		int[] count = new int[2];
		for(CableWire temp: inputEdges){
			if(temp.getFirstLocation().equals(source)){
				count[0]++;
			}
			if(temp.getSecondLocation().equals(dest)){
				count[1]++;
			}
		}
		if(count[0]<1 || count[1]<1)
			throw new IllegalArgumentException();
		Set<CableWire> mst = getMst(inputEdges);
		if(mst == null)
			return null;
		//generate a new graph from the minimum spanning tree
		GeneralGraph<String,Edge<String>> graph = new GeneralGraph<String,Edge<String>>();
		for(CableWire wire: mst){
			graph.addVertex(wire.getFirstLocation());
			graph.addVertex(wire.getSecondLocation());
			graph.addEdge(new Edge<String>(wire.getFirstLocation(),wire.getSecondLocation(),wire.getCost()));
			graph.addEdge(new Edge<String>(wire.getSecondLocation(),wire.getFirstLocation(),wire.getCost()));
		}
		//use Dijkstra to find the lowest cost path
		Dijkstra dk = new Dijkstra();
		List<Edge<String>> temp= dk.shortestPath(graph, source, dest);
		if(temp == null)
			return null;
		//add the result back to a cablewire set
		List<CableWire> res = new ArrayList<CableWire>();
		for(Edge<String> edge : temp){
			res.add(new CableWire(edge.src(),edge.dest(),edge.weight()));
		}
		return res;
	}
}
